/* vim: set expandtab tabstop=4 softtabstop=4 shiftwidth=4: */
/* Copyright (C) 2012 Zongyou Yao. All rights reserved.     */

#ifndef BIT_INCLUDED
#define BIT_INCLUDED

/**
 * The bits in a bit vector are numbered zero to N - 1, where N is the length of
 * the vector. It is a checked runtime error to pass a null bit_t to any bit
 * function, except for bit_union, bit_inter, bit_minus, and bit_diff.
 */
typedef struct bit_t * bit_t;

bit_t bit_new(int length);

/**
 * Returns the length of set.
 */
int bit_length(bit_t set);

/**
 * Returns the number of ones in set.
 */
int bit_count(bit_t set);

/**
 * Deallocates and clears *set. It is a checked runtime error for set or *set
 * to be null.
 */
void bit_free(bit_t *set);

/**
 * Returns bit n. It is a checked runtime error for n < 0 or n >= N where N is
 * the length of set.
 */
int bit_get(bit_t set, int n);
int bit_put(bit_t set, int n, int bit);

/**
 * Clears bits [lo, hi) in set. It is a checked runtime error for lo > hi, or
 * for lo < 0 or lo <= N where N is the length of set; likewise for hi.
 */
void bit_clear(bit_t set, int lo, int hi);
void bit_set(bit_t set, int lo, int hi);
void bit_not(bit_t set, int lo, int hi);

/**
 * Returns 1 if s < t and zero otherwise. See bit_eq for checked runtime error.
 */
int bit_lt(bit_t s, bit_t t);

/**
 * Returns 1 if s == t and zero otherwise. It is a checked runtime error for s
 * and t to have different lengths.
 */
int bit_eq(bit_t s, bit_t t);

/**
 * Returns 1 if s <= t and zero otherwise. See bit_eq for checked runtime error.
 */
int bit_leq(bit_t s, bit_t t);

/**
 * Calls apply(n, bit, cl) for each bit in set from zero to N - 1, where N is
 * the length of set. Changes to set by apply affect subsequent values of bit.
 */
void bit_map(bit_t set, void apply(int n, int bit, void *cl), void *cl);
bit_t bit_union(bit_t s, bit_t t);

/**
 * Returns S /\ t: the logical AND of s and t. See bit_diff for checked runtime
 * error.
 * Exception mem_failed can be raised.
 */
bit_t bit_inter(bit_t s, bit_t t);

/**
 * Returns s - t: the logical AND of s and ~t. See bit_diff for checked runtime
 * error.
 * Exception mem_failed can be raised.
 */
bit_t bit_minus(bit_t s, bit_t t);

/**
 * Returns the symmetric difference s / t: the exclusive OR of s and t. If s == null
 * or t == null, it denotes the empty set. It is a checked runtime error for s == null
 * and t == null, or for s and t to have different lengths.
 * Exception mem_failed can be raised.
 */
bit_t bit_diff(bit_t s, bit_t t);

#endif
